/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    //方法一：原地拷贝
    public Node copyRandomList(Node head) {
        if(head == null) {
            return head;
        }

        //先new 节点 放到 对应链表元素的后面
        Node cur = head;
        while(cur!= null) {//修改一
            //new 新节点
            Node node = new Node(cur.val);

            Node curNext = cur.next;

            cur.next = node;

            node.next = curNext;

            cur = curNext;
        }

        //复制random

        cur = head;
        while(cur != null && cur.next != null) {
            //最后得加next,不然新链表连的还是原链表的节点
            if(cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        //得到自己的链表(也就是调整源链表和新链表的next指针)
        //注意源链表的指针也得回去
        cur = head;
        Node ret = cur.next;
        while(cur != null && cur.next != null) {
            Node my = cur.next;

            cur.next = my.next;

            cur = my;
        }

        return ret;

    }
}